package leetcode.f1t100;

import leetcode.struct.ListNode;

/**
 * 链表小于目标值的放前面, 大于目标值的放后面, 分类后的相对位置不变
 * https://leetcode.com/problems/partition-list/
 *
 * @author lichx
 * @createTime 2024/1/31 10:08
 */
public class Q86_PartitionList {

    public static void main(String[] args) {
        Q86_PartitionList bean = new Q86_PartitionList();
        ListNode list = new ListNode(3, new ListNode(2, new ListNode(3)));
        ListNode partition = bean.partition(list, 3);
        while(partition!= null) {
            System.out.println(partition.val);
            partition = partition.next;
        }
    }

    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(), big = new ListNode(), scur = small, bcur = big;
        while(head != null) {
            if(head.val < x) {
                scur.next = head;
                scur = scur.next;
            } else {
                bcur.next = head;
                bcur = bcur.next;
            }
            head = head.next;
        }
        bcur.next = null;
        scur.next = big.next;
        return small.next;
    }



}
